W1. Введение в теоретическую информатику, золотое сечение и Фибоначчи, структура курса, модели вычислений

Автор

Manuel Mazzara

Дата публикации

29 января 2026 г.

1. Краткое содержание

1.1 Золотое сечение и последовательность Фибоначчи

Золотое сечение (обозначается греческой буквой \(\phi\), читается «фи») — особое иррациональное число, приблизительно равное 1,618. Как и \(\pi\) (пи), золотое сечение — иррациональное число: его десятичные знаки продолжаются бесконечно без периодического повторения. Это число встречается в природе, искусстве, архитектуре и математике и часто связывается с эстетически приятными пропорциями.

1.1.1 Последовательность Фибоначчи

Последовательность Фибоначчи — это последовательность чисел, в которой каждое число равно сумме двух предыдущих. Она начинается так: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Математически её можно задать так:

\(F_1 = 1\)
\(F_2 = 1\)
\(F_n = F_{n-1} + F_{n-2}\) при \(n > 2\)

Последовательность Фибоначчи замечательно связана с золотым сечением. Если делить каждое число Фибоначчи на предыдущее, получая последовательность отношений, эта последовательность сходится к \(\phi\).

Что значит «сходится»? В математике говорят, что последовательность сходится к значению \(L\), если её члены сколь угодно приближаются к \(L\) по мере удаления вдоль последовательности. Как бы мало вы ни выбрали расстояние (скажем, 0,001 или 0,0000001), рано или поздно все члены после некоторого места окажутся внутри этой окрестности \(L\). Члены никогда не достигают \(L\) точно, но становятся бесконечно близки к нему.

1.1.2 Сходимость к золотому сечению

Рассмотрим отношения \(r(n) = \frac{F_{n+1}}{F_n}\):

\(r(1) = \frac{1}{1} = 1\)
\(r(2) = \frac{2}{1} = 2\)
\(r(3) = \frac{3}{2} = 1.5\)
\(r(4) = \frac{5}{3} = 1.67\)
\(r(5) = \frac{8}{5} = 1.6\)
\(r(6) = \frac{13}{8} = 1.625\)
\(r(7) = \frac{21}{13} = 1.6125\)

Продолжая, мы видим, что эти отношения приближаются к \(\phi = 1.61803398...\)

Наблюдается интересная закономерность: члены с нечётными индексами (1-й, 3-й, 5-й, …) все меньше золотого сечения, а члены с чётными индексами (2-й, 4-й, 6-й, …) все больше золотого сечения. Последовательность сходится к \(\phi\) то сверху, то снизу, с каждым шагом всё ближе подходя к нему.

Точное значение золотого сечения можно записать так: \[\phi = \frac{1 + \sqrt{5}}{2}\]

Эта формула получается из уравнения \(x^2 = x + 1\), которое отражает свойство самоподобия золотого сечения: \(\phi^2 = \phi + 1\). То есть если возвести \(\phi\) в квадрат, получится \(\phi\) плюс 1 — в духе рекурсивной природы последовательности Фибоначчи.

1.1.3 Золотой прямоугольник и золотая спираль

Золотой прямоугольник — прямоугольник, стороны которого находятся в отношении золотого сечения (длина к ширине = \(\phi\)). Если из золотого прямоугольника вырезать квадрат, оставшийся прямоугольник снова будет золотым. Это позволяет строить вложенную картину из квадратов и прямоугольников.

Разбиение золотого прямоугольника на квадраты размеров из ряда Фибоначчи

Если провести дуги четверти круга через противоположные углы каждого квадрата в таком расположении золотого прямоугольника (со сторонами квадратов 1, 1, 2, 3, 5, 8, …), получится золотая спираль, также называемая спиралью Фибоначчи. Такая спираль часто встречается в природе.

1.2 Золотое сечение в природе и в деятельности человека

1.2.1 Золотое сечение в анатомии человека

Золотое сечение проявляется в пропорциях тела человека. Например, костяшки пальцев (фаланги) по длине приблизительно подчиняются последовательности Фибоначчи. Отношение длин соседних фаланг стремится к золотому сечению. Такое устройство позволяет кисти при сжатии в кулак образовывать удобный изгиб: кончики пальцев следуют по спиральной траектории.

Черты лица также часто близки к пропорциям золотого сечения. Положение уха, подбородка, носа и других элементов лица нередко согласуется с наложением золотой спирали, что многие связывают с визуальным восприятием красоты лица.

1.2.2 Золотое сечение в архитектуре

Архитекторы и дизайнеры столетиями использовали золотое сечение для создания гармоничных построек. Пример — лестница Браманте в Музеях Ватикана (архитектор Джузеппе Момо, 1932): двойная спиральная лестница демонстрирует спиральную геометрию, связанную с золотым сечением.

Средневековые европейские соборы нередко строились на основе сакральной геометрии — использования математических пропорций для выражения духовных идей и «показа мира через математику» как пути к лучшему пониманию божественного. Архитектор эпохи Возрождения Леон Баттиста Альберти написал трактат De re aedificatoria (Об искусстве строить, 1443–1452), где описывал идеальную церковь в терминах духовной геометрии с кругами, квадратами и пропорциями.

Знаменитый Витрувианский человек Леонардо да Винчи (около 1490 г.) иллюстрирует пропорции тела по древнему архитектору Витрувию и принципы сакральной геометрии: человеческая фигура вписывается и в круг, и в квадрат.

1.2.3 Золотое сечение в музыке

Композиторы и мастера инструментов сотни лет опирались на ряд Фибоначчи и золотое сечение. Показательный пример — первая фортепианная соната Моцарта. В первой части всего 100 тактов:

Экспозиция: 38 тактов (обозначим \(A\))
Разработка и реприза: 62 такта (обозначим \(B\))
Отношение: \(\frac{B}{A} = \frac{62}{38} = 1.6\)

Это отношение заметно близко к золотому сечению. Сознательно ли это делал Моцарт или интуитивно — открытый вопрос.

Легендарный скрипичный мастер Страдивари проектировал инструменты с пропорциями, основанными на золотом сечении. Отношения длины корпуса, верхней и нижней «окружностей» (bout) у скрипок Страдивари близки к \(\phi\), что, возможно, способствует их знаменитому звучанию.

1.2.4 Золотое сечение в современном дизайне

Многие корпоративные логотипы строятся на геометрии золотого сечения. Примеры:

Twitter/X: силуэт птицы из пересекающихся окружностей, радиусы которых связаны пропорциями золотого сечения
National Geographic: жёлтый прямоугольник со сторонами в отношении золотого сечения (1 : 1,618)
Chevron: ленты с пропорциями 1 и 1,618
BP: концентрические круги в «солнечном» знаке следуют золотому сечению
Pepsi: круговой знак с окружностями, диаметры которых в отношении золотого сечения
Toyota: три овала вписаны в прямоугольник с пропорцией 1,618

Золотое сечение широко используют, потому что оно даёт композиции, которые человеческому глазу кажутся эстетически удачными.

1.3 Математика и её практические приложения

1.3.1 Неожиданная полезность чистой математики

Джон фон Нейман, один из крупнейших математиков XX века, формулировал важную мысль о связи чистой математики и практики. В выступлении 1954 года «Роль математики в науке и обществе» он сказал:

«Большая часть математики, которая становится полезной, развивалась совершенно без намерения быть полезной, в ситуации, когда никто не мог знать, в какой области она пригодится; не было и общих признаков, что это когда-либо случится».

Фон Нейман также отмечал:

«В целом для математики равномерно верно, что между математическим открытием и моментом, когда оно становится полезным, проходит время; это может быть от 30 до 100 лет, а иногда и больше; и вся система, похоже, работает без всякого направления, без ориентации на полезность и без стремления делать полезные вещи».

Этот принцип важен для теоретической информатики: многие математические идеи, развитые столетия назад без практических целей, стали основой современных вычислений.

1.3.2 Исторический пример: теория чисел и криптография

Яркая иллюстрация принципа фон Неймана — связь теории чисел с современной криптографией. Теория чисел — раздел чистой математики о свойствах целых чисел; её развивали века без мысли о прикладных задачах.

Однако современные криптосистемы целиком опираются на теорию чисел:

Шифрование RSA (широко применяется для защищённой связи в интернете) основано на трудности разложения больших чисел на множители — чисто теоретико-числовой задаче
Bitcoin и другие криптовалюты используют криптографию на теоретико-числовых задачах
В 1994 году криптография столкнулась с фундаментальным вызовом: Питер Шор показал, что квантовые компьютеры могут эффективно решать теоретико-числовые задачи, лежащие в основе RSA и подобных систем

Отсюда важный вопрос: станет ли небезопасной любая криптосхема на теоретико-числовых задачах, когда квантовые компьютеры станут практичными? Этим вопросом задаётся исследование постквантовой криптографии.

1.4 Что такое теоретическая информатика?

Теоретическая информатика (Theoretical Computer Science, TCS) — математическое изучение самого процесса вычисления. Прикладная информатика строит системы и пишет программы; теоретическая задаёт фундаментальные вопросы:

Что можно вычислить?
Что нельзя вычислить?
Насколько эффективно решаются задачи?
Каковы предельные возможности вычислений?

1.4.1 Вычислимость и сложность

Два центральных понятия:

Вычислимость: что можно вычислить, без учёта времени и ресурсов. Задача вычислима, если существует алгоритм, который её решает (даже если он работал бы миллиарды лет).
Сложность: насколько эффективно можно решать задачи. Даже вычислимая задача может требовать столько времени или памяти, что на практике неразрешима. Эффективность описывают с помощью асимптотической о-нотации, например \(\mathcal{O}(n)\) для линейного времени или \(\mathcal{O}(n \log n)\) для типичных сортировок.

Что такое O-большое? O-большое описывает, как время работы или объём памяти алгоритма растут с ростом размера входа. Например:

\(\mathcal{O}(1)\): константное время — не зависит от размера входа
\(\mathcal{O}(n)\): линейное время — при удвоении входа время примерно удваивается
\(\mathcal{O}(n^2)\): квадратичное время — при удвоении входа время примерно учетверяется
\(\mathcal{O}(n \log n)\): типичная оценка для эффективных сортировок

Знаменитая проблема P против NP спрашивает, верно ли, что всякую задачу, решение которой можно быстро проверить, можно и быстро найти — одна из главных нерешённых задач информатики и математики.

1.4.2 Зачем изучать теоретическую информатику?

Понимание теоретической информатики важно по нескольким причинам:

Понимание компиляторов: компилятор переводит языки высокого уровня в машинный код; здесь не обойтись без формальных грамматик, теории автоматов и распознавания языков. Без этих основ нельзя по-настоящему понять устройство языков программирования.
Пределы вычислимости: как в физике нельзя ускоряться бесконечно из-за трения и энергии, так теория вычислимости показывает фундаментальные ограничения возможностей компьютера. Это уберегает от попыток решить заведомо невозможное.
Лучшее решение задач: разработчик, не понимающий работу компилятора, «не лучше хорошего пилота, когда нужно чинить двигатель». Теория помогает выходить за рамки средних решений и по-настоящему оптимизировать системы.
Историческая перспектива: знание великих имён и результатов, на которых стоит современная техника, помогает ориентироваться в технологиях и изобретать дальше.

1.5 Сведения о курсе и структура курса

1.5.1 Предварительные требования

Курс рассчитан на относительную самодостаточность, но полезны базовые знания:

Логика: высказывания, доказательства, рассуждения
Дискретная математика: множества, отношения, функции, приёмы доказательств
Алгоритмы и структуры данных: базовое алгоритмическое мышление (желательно, но не обязательно)
Математический анализ I: общая математическая зрелость (менее критично, чем остальное)

По ходу курса при необходимости повторяются нужные математические основы.

1.5.2 Темы курса

Курс охватывает такие разделы:

Свойства языков: операции над языками, оператор Клини (звезда Клини), мощность языка
FSA (finite state automaton): простейшая модель вычислений
PDA (pushdown automaton): автоматы с памятью в виде стека
Регулярные выражения и регулярные языки: шаблоны и описание языков
Связи автоматов и языков: лемма о накачке, свойства замкнутости
Формальные грамматики: иерархия Хомского и порождающие правила
TM (Turing machine): самая мощная из стандартных моделей
Теория вычислимости: проблема останова, тьюрингова вычислимость, теорема Райса
\(\lambda\)-исчисление: альтернативная модель вычислений (по возможности времени)

1.5.3 Структура курса и оценивание

Расписание по неделям:

Лекции: четверг 09:00–10:30, ауд. 108
Практические занятия: четверг 10:40–12:10 (все группы, ауд. 108)
Лабораторные: четверг днём (12:40–19:10, аудитории по группам)

Лабораторные начинаются 29 января 2026 г. и обычно соответствуют теме предыдущей недели.

Нагрузка: курс даёт 6 кредитов, ориентир — около 10 часов в неделю:

6 часов лекций, практик и лабораторных
4–6 часов самостоятельной работы

Оценивание (100 основных баллов + 5 за активность, всего до 105):

Промежуточный экзамен: 30 баллов
Итоговый экзамен: 30 баллов
Домашние задания: 40 баллов (два задания)
Активность: 5 баллов

Задания выходят примерно на 6-й неделе (конец февраля / начало марта 2026) и на 13-й неделе (вторая половина апреля 2026).

1.5.4 Ресурсы курса

Рекомендуемые учебники:

J.E. Hopcroft и J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison Wesley (1979).
M. Davis, R. Sigal и E.J. Weyuker. Computability, complexity, and languages: fundamentals of theoretical computer science. 2-е изд., Academic Press (1994).
J. Hromkovic. Algorithmic Adventures: From Knowledge to Magic. Springer (2009).

Материалы, оценки и объявления — на Moodle: [S26] Theoretical Computer Science.

1.6 Исторический контекст и хронология

Теоретическую информатику лучше понимать в историческом развитии:

ок. 600 г. до н. э.: парадокс Эпименида («все критяне лжецы») поднимает вопросы самоссылки в логике.
1936: между мировыми войнами Алан Тьюринг доказал, что не существует (и не может существовать) общего метода, который для произвольного алгоритма и входа определяет, остановится ли вычисление — проблема останова; фундаментальный результат теории вычислимости.
1956: Ноам Хомский описал иерархию грамматик (иерархия Хомского), классифицируя формальные языки по типу порождающих грамматик; это стало основой для компиляторов и теории языков.
1467: ещё раньше Леон Баттиста Альберти изобрёл шифр Альберти — один из первых полиалфавитных шифров, демонстрируя раннюю связь математики с кодированием информации.

Компиляция — перевод кода высокого уровня в машинный — сегодня кажется простой, но опирается на века математических и логических открытий.

1.7 Базовые понятия: языки и строки

Прежде чем изучать модели вычислений, нужно понять, что именно они обрабатывают. В теоретической информатике вычисление часто описывают как обработку строк (strings), чтобы определить, принадлежат ли они заданным языкам (languages).

1.7.1 Алфавит, строки и языки

Alphabet — конечное непустое множество символов. Его обычно обозначают греческой буквой \(\Sigma\) (сигма). Примеры:

\(\Sigma_1 = \{0, 1\}\) (двоичный алфавит)
\(\Sigma_2 = \{a, b, c, \ldots, z\}\) (строчные латинские буквы)
\(\Sigma_3 = \{(, ), +, -, \times, \div\}\) (математические символы)

String (или word) — конечная последовательность символов алфавита. Если \(\Sigma = \{0, 1\}\), то \(0101\), \(1100\) и \(0\) — строки над \(\Sigma\). Empty string (без символов) обозначается \(\epsilon\) (эпсилон) или \(\lambda\) (лямбда).

Length строки \(w\), обозначение \(|w|\), — число её символов. Например:

\(|0101| = 4\)
\(|hello| = 5\)
\(|\epsilon| = 0\)

Language \(L\) — множество строк над алфавитом \(\Sigma\). Это математическое определение, не то же самое, что языки вроде Python или Java (хотя связь позже проявится). Примеры:

\(L_1 = \{0, 01, 011, 0111, \ldots\}\) — строки, начинающиеся с \(0\), за которым идут любое число единиц
\(L_2 = \{\epsilon, 00, 0000, 000000, \ldots\}\) — строки с чётным числом нулей
\(L_3 = \{w : w \text{ содержит равное число } 0\text{ и } 1\}\)

Языки бывают:

Конечными: \(L = \{hello, world\}\) ровно из двух строк
Бесконечными: \(L = \{0^n : n \geq 0\} = \{\epsilon, 0, 00, 000, \ldots\}\)

1.7.2 Что значит «распознавать» или «принимать»?

Когда говорят, что автомат распознаёт или принимает язык \(L\), имеют в виду:

На вход подаётся произвольная строка \(w\); автомат читает её символ за символом
После прочтения всех символов автомат либо выдаёт Accept («да, \(w \in L\)»), либо Reject («нет, \(w \notin L\)»)
Он принимает в точности те строки, которые входят в \(L\), и отвергает все остальные

Пример: язык \(L = \{w : w \text{ содержит чётное число } 1\}\) над алфавитом \(\{0, 1\}\).

Автомат для \(L\):

Принимает: \(\epsilon\) (ноль единиц — чётно), \(11\), \(0110\), \(1001\)
Отвергает: \(1\), \(001\), \(111\), \(0101\)

Автомат не «вычисляет число» и не возвращает значение — он даёт бинарный ответ: Accept или Reject.

1.8 Модели вычислений

Model of computation — математическая абстракция того, как протекает вычисление. Разные модели отражают разную вычислительную мощность (computational power).

1.8.1 Базовая модель компьютера

На самом верхнем уровне вычисление включает:

ЦПУ (центральный процессор): выполняет операции
Память: хранит данные и команды
Ввод/вывод: получает данные и выдаёт результат

Базовая модель компьютера: ввод, ЦПУ, память и вывод (как взаимодействие компонентов)

ЦПУ выполняет команды из памяти программы, использует временную память для промежуточных результатов, читает ввод и формирует вывод.

Пример: вычислить \(f(x) = x^3\) при \(x = 2\)

В памяти программы лежат инструкции:
- вычислить \(x \times x\) (получится \(x^2\))
- вычислить \(x^2 \times x\) (получится \(x^3\))
Ввод: \(x = 2\)
Обработка:
- во временной памяти: \(z = 2 \times 2 = 4\)
- во временной памяти: \(f(x) = z \times 2 = 8\)
Вывод: \(f(x) = 8\)

1.8.2 Абстракция автомата

Automaton — модель, в которой ЦПУ представлено как множество states (конфигураций) и transitions (правил смены состояния при вводе). Автомат по-прежнему взаимодействует с памятью, вводом и выводом.

Абстракция автомата: конечное управление, ввод, память и вывод

Что такое состояние? State — текущая конфигурация или «режим» автомата. Наглядные аналогии:

Светофор: состояния КРАСНЫЙ, ЖЁЛТЫЙ, ЗЕЛЁНЫЙ
Торговый автомат: ОЖИДАНИЕ, МОНЕТЫ ВНЕСЕНЫ, ВЫДАЧА
Компьютер: РАБОТА, СОН, ВЫКЛЮЧЕН

Что такое переход? Transition — правило: при данном входе перейти из одного состояния в другое. Например:

Светофор: «в ЗЕЛЁНОМ и прошло 30 с → ЖЁЛТЫЙ»
Автомат: «в \(q_1\) и прочитан символ \(0\) → \(q_2\)»

У разных типов автоматов разные возможности памяти, отчего и разная вычислительная сила.

1.8.3 Три типа автоматов

1. FSA (finite state automaton)

Память (Memory): нет внешней временной памяти; информация только в текущем состоянии (state)
Мощность: «небольшая»
Примеры: лифты, торговые автоматы, простой поиск шаблонов
Распознаваемые языки: регулярные языки (Regular languages)

У FSA фиксированное число состояний; он может «помнить» лишь ограниченный объём информации, закодированный состоянием.

FSA для строк с чётным числом единиц

Конкретный пример (FSA):

Спроектируем FSA для языка \(L = \{w : w \text{ содержит чётное число } 1\}\) над \(\{0, 1\}\).

Нужны два состояния:

\(q_0\) (EVEN): «видели чётное число единиц»
\(q_1\) (ODD): «видели нечётное число единиц»

Переходы:

Из \(q_0\): прочитали \(0\) → остаёмся в \(q_0\) (нули не меняют чётность)
Из \(q_0\): прочитали \(1\) → \(q_1\) (чётное → нечётное)
Из \(q_1\): прочитали \(0\) → остаёмся в \(q_1\)
Из \(q_1\): прочитали \(1\) → \(q_0\) (нечётное → чётное)

Начальное состояние: \(q_0\) (ноль единиц — чётно)
Принимающее состояние: \(q_0\) (конец в EVEN)

Прослеживание для строки “0110”:

Старт в \(q_0\) (EVEN)
Читаем \(0\) → остаёмся в \(q_0\) (0 единиц)
Читаем \(1\) → \(q_1\) (1 единица)
Читаем \(1\) → \(q_0\) (2 единицы)
Читаем \(0\) → \(q_0\) (по-прежнему 2 единицы)
Конец в \(q_0\) (принимающее) → ПРИНЯТЬ ✓

FSA верно принимает “\(0110\)”: в строке две единицы.

2. PDA (pushdown automaton)

Память (Memory): стек (stack) (структура «последним пришёл — первым ушёл»)
Операции: push (положить в стек) и pop (снять со стека, деструктивно)
Мощность: «средняя»
Примеры: разбор в компиляторах, вложенные конструкции
Распознаваемые языки: контекстно-свободные языки (Context-free languages)

PDA распознают более сложные закономерности, чем FSA, например сбалансированные скобки или вложенность в языках программирования.

Идея PDA для aⁿbⁿ: push при чтении a, затем pop при чтении b

Что такое стек? Stack — структура «последним вошёл — первым вышел» (LIFO), как стопка тарелок:

Push: положить элемент сверху
Pop: снять верхний (доступен только он)

Как стопка книг: класть и брать можно только сверху.

Конкретный пример (PDA):

Язык \(L = \{a^n b^n : n \geq 0\}\) (одинаковое число \(a\) подряд, затем столько же \(b\)).

Примеры из \(L\): \(\epsilon\), \(ab\), \(aabb\), \(aaabbb\), …
Примеры не из \(L\): \(a\), \(ba\), \(aab\), \(abb\), …

Стратегия:

На каждую \(a\) — push в стек (считаем \(a\))
На каждую \(b\) — pop \(a\) (сопоставляем \(b\) с \(a\))
Принимаем, если ввод исчерпан и стек пуст (числа совпали)

Прослеживание для “aabb”:

\(a\) → push \(A\). Стек: [\(A\)]
\(a\) → push \(A\). Стек: [\(A\), \(A\)]
\(b\) → pop \(A\). Стек: [\(A\)]
\(b\) → pop \(A\). Стек: []
Ввод кончился, стек пуст → ПРИНЯТЬ ✓

Почему FSA не справляется: у FSA нет stack, он не может запомнить произвольное число \(a\). С \(n\) states автомат различает не больше \(n\) классов префиксов ввода, поэтому, например, нельзя отличить длинные префиксы вида \(a^{1000}\) и \(a^{1001}\) — это следует из pigeonhole principle (принципа Дирихле). Stack даёт PDA неограниченную возможность сопоставлять совпадения.

3. TM (Turing machine)

Память (Memory): бесконечная лента (tape) (по сути модель оперативной памяти с произвольным доступом)
Мощность: «максимальная» из стандартных моделей
Примеры: любой вычислимый алгоритм
Распознаваемые языки: рекурсивно перечислимые языки (Recursively enumerable languages)

TM может вычислять всё вычислимое. Лента формально последовательна, но это не ограничивает вычислительную мощность.

Модель машины Тьюринга: читающая/пишущая головка на неограниченной ленте

Что такое лента у TM? Tape — бесконечная последовательность ячеек с символами. Read/write head может:

прочитать символ в текущей ячейке
записать новый символ (стирая старый)
сдвинуться влево или вправо на соседнюю ячейку

Как бесконечная полоска с ячейками, по которой можно двигать «карандаш».

Почему это сильнее стека? В отличие от стека (доступ только к вершине), TM может:

перемещаться по ленте и снова читать старые данные
перезаписывать (не только «съедать» символы, как при pop)
использовать ленту для черновых вычислений

Пример задачи для TM, но не для PDA:

Язык \(L = \{a^n b^n c^n : n \geq 0\}\) (равное число \(a\), \(b\) и \(c\)).

Примеры из \(L\): \(\epsilon\), \(abc\), \(aabbcc\), …

TM может:

Зачеркнуть по одному \(a\), \(b\) и \(c\)
Вернуться в начало
Повторять, пока не закончатся символы
Принять, если все три типа исчерпались одновременно

Одному стеку недостаточно, чтобы считать три независимые величины. Поэтому TM строго мощнее PDA.

1.8.4 Иерархия мощности

Что значит «вычислительная мощность»? Одна модель «сильнее» другой, если она распознаёт больший класс языков (задач). Аналогия с инструментами:

Отвёртка (FSA) — для винтов
Дрель (PDA) — и винты, и сверление
Мастерская (TM) — ещё шире

Иерархия строгая:

\[\text{Finite Automata} < \text{Pushdown Automata} < \text{Turing Machine}\]

То есть:

Всё, что решает FSA, решает и PDA
Всё, что решает PDA, решает и TM
Есть задачи для PDA, но не для FSA (например \(a^n b^n\))
Есть задачи для TM, но не для PDA (например \(a^n b^n c^n\))

Дополнительная память (стек у PDA, лента у TM) и даёт большую мощность.

1.9 Вопрос на весь курс: неразрешимые задачи

TM (Turing machine) — самая мощная из известных информатике моделей. Любой алгоритм на любом языке программирования можно смоделировать TM.

Возникает вопрос: существуют ли задачи, которые не решает даже TM?

Ответ: да. Есть неразрешимые задачи — для которых не существует алгоритма даже в принципе. Мы подробно разберём, что это значит, почему так и какие следствия для информатики.

Самый известный пример — проблема останова: по произвольной программе и входу определить, завершится ли выполнение или оно будет длиться бесконечно. Алан Тьюринг в 1936 году доказал, что ни один алгоритм не решает эту задачу для всех возможных пар программа–вход.

Почему это важно на практике?

Нельзя написать программу, которая для любой другой гарантированно обнаруживает бесконечный цикл
Нельзя гарантировать обнаружение всех ошибок, приводящих к зависанию
Есть фундаментальные пределы автоматической верификации ПО

Это одно из глубочайших открытий в математике и информатике: не всякая чётко сформулированная вычислительная задача разрешима. Некоторые задачи неразрешимы не потому, что мы ещё не придумали алгоритм, а потому что никакого алгоритма не существует.

2. Определения

Golden ratio (\(\phi\)): иррациональное число ≈ 1,618; предел отношений соседних чисел Фибоначчи; встречается в природе, искусстве и математике.
Irrational number: вещественное число, невыразимое как отношение двух целых; десятичная запись бесконечна и непериодична.
Convergence: свойство последовательности неограниченно приближаться к предельному значению; отношения Фибоначчи сходятся к \(\phi\).
Fibonacci sequence: каждый член — сумма двух предыдущих, начало 1, 1: \(F_n = F_{n-1} + F_{n-2}\) при \(n > 2\).
Golden rectangle: прямоугольник со сторонами в отношении золотого сечения (длина/ширина = \(\phi\)).
Golden spiral: логарифмическая спираль с ростом на коэффициент \(\phi\) за четверть оборота; часто аппроксимируется квадратами Фибоначчи.
Сакральная геометрия: использование геометрических пропорций и фигур в культовой архитектуре и искусстве для выражения духовных представлений.
Шифр Альберти: раннее устройство полиалфавитного шифра (вращающиеся концентрические диски), Л. Б. Альберти, 1467.
Number theory: раздел чистой математики о свойствах целых чисел и родственных объектах.
Криптография: обеспечение секретности передачи данных с помощью шифрования и расшифрования.
RSA: широко используемая криптосистема с открытым ключом на трудности разложения больших чисел.
Квантовый компьютер: вычислительное устройство на квантомеханических эффектах; для ряда задач потенциально быстрее классического.
Theoretical computer science (TCS): математическое изучение вычислений: что вычислимо, сложность, пределы вычислений.
Alphabet (\(\Sigma\)): конечное непустое множество символов для построения строк; например \(\{0, 1\}\) — двоичный алфавит.
String (word): конечная последовательность символов алфавита; например \(0101\) над двоичным алфавитом.
Empty string (\(\epsilon\) или \(\lambda\)): строка без символов, длина ноль.
String length (\(|w|\)): число символов; например \(|hello| = 5\), \(|\epsilon| = 0\).
Language: множество строк над алфавитом; может быть конечным или бесконечным.
Accept / recognize: Accept, если после обработки автомат в accepting state; recognizes язык \(L\), если принимает ровно строки из \(L\).
Computability: какие задачи решаются алгоритмами без ограничения по ресурсам.
Complexity: насколько эффективно (по времени и памяти) решаются задачи.
Big-O (\(\mathcal{O}\)): asymptotic notation для роста времени или памяти алгоритма с размером входа; \(\mathcal{O}(n)\) — linear time, \(\mathcal{O}(n^2)\) — quadratic time.
Computational power: класс языков (задач), решаемых моделью; чем выше мощность, тем больше языков.
P vs NP problem: крупная нерешённая задача о равенстве классов быстро проверяемых и быстро решаемых задач.
Automaton: математическая модель вычисления из states и transitions для распознавания или порождения языков.
State: конфигурация автомата в данный момент вычисления.
Transition: правило смены состояния в зависимости от входа.
FSA (finite state automaton): конечное число состояний, без внешней памяти; распознаёт regular languages (регулярные языки).
PDA (pushdown automaton): конечное управление плюс stack; распознаёт context-free languages (контекстно-свободные языки).
TM (Turing machine): конечное управление плюс бесконечная tape; вычисляет всё вычислимое.
Stack: структура LIFO с операциями push и pop.
Regular language: класс языков, распознаваемых FSA.
Context-free language: класс языков, распознаваемых PDA; включает синтаксис большинства языков программирования.
Recursively enumerable language: класс языков, распознаваемых TM.
Halting problem: определить, остановится ли программа на данном входе; её неразрешимость доказал Тьюринг в 1936 году.
Undecidable problem: не существует алгоритма, решающего все её экземпляры.
Formal grammar: набор production rules для порождения строк формального языка.
Chomsky hierarchy: классификация грамматик на четыре типа (0–3) по порождающей силе; Н. Хомский, 1956.
Compiler: программа, переводящая исходный код с языка высокого уровня в машинный или более низкий уровень.
\(\lambda\)-calculus: формальная система вычислений через абстракцию и применение функций; А. Чёрч.

3. Формулы

Последовательность Фибоначчи: \(F_1 = 1\), \(F_2 = 1\), \(F_n = F_{n-1} + F_{n-2}\) при \(n > 2\)
Отношение Фибоначчи: \(r(n) = \frac{F_{n+1}}{F_n}\), сходится к \(\phi\) при \(n \to \infty\)
Золотое сечение: \(\phi = \lim_{n \to \infty} \frac{F_{n+1}}{F_n} \approx 1.61803398...\)
Точное значение \(\phi\): \(\phi = \frac{1 + \sqrt{5}}{2}\)

4. Примеры

4.1. Вычислить начальные отношения Фибоначчи (Лекция 1, Пример 1)

Вычислите первые семь отношений \(r(n) = \frac{F_{n+1}}{F_n}\) для последовательности Фибоначчи и проследите за их поведением.

Показать решение

Ключевая идея: Фибоначчи заданы как \(F_1 = 1\), \(F_2 = 1\), \(F_n = F_{n-1} + F_{n-2}\). Вычисляем последовательные отношения и наблюдаем сходимость к золотому сечению.

Числа Фибоначчи:
- \(F_1 = 1\)
- \(F_2 = 1\)
- \(F_3 = F_2 + F_1 = 1 + 1 = 2\)
- \(F_4 = F_3 + F_2 = 2 + 1 = 3\)
- \(F_5 = F_4 + F_3 = 3 + 2 = 5\)
- \(F_6 = F_5 + F_4 = 5 + 3 = 8\)
- \(F_7 = F_6 + F_5 = 8 + 5 = 13\)
- \(F_8 = F_7 + F_6 = 13 + 8 = 21\)
Отношения \(r(n) = \frac{F_{n+1}}{F_n}\):
- \(r(1) = \frac{F_2}{F_1} = \frac{1}{1} = 1.000\)
- \(r(2) = \frac{F_3}{F_2} = \frac{2}{1} = 2.000\)
- \(r(3) = \frac{F_4}{F_3} = \frac{3}{2} = 1.500\)
- \(r(4) = \frac{F_5}{F_4} = \frac{5}{3} \approx 1.667\)
- \(r(5) = \frac{F_6}{F_5} = \frac{8}{5} = 1.600\)
- \(r(6) = \frac{F_7}{F_6} = \frac{13}{8} = 1.625\)
- \(r(7) = \frac{F_8}{F_7} = \frac{21}{13} \approx 1.615\)
Закономерность:
- Отношения с нечётными индексами (\(r(1), r(3), r(5), r(7)\): 1,000; 1,500; 1,600; 1,615) меньше \(\phi \approx 1.618\)
- С чётными (\(r(2), r(4), r(6)\): 2,000; 1,667; 1,625) больше \(\phi \approx 1.618\)
- Отношения колеблются вокруг \(\phi\), сходясь сверху и снизу

Ответ: Отношения равны 1, 2, 1,5, 1,67, 1,6, 1,625, 1,6125 и сходятся к золотому сечению \(\phi \approx 1.618\).

4.2. Определить модель вычислений (Лекция 1, Пример 2)

Для каждой системы укажите, какая модель (FSA, PDA или TM) лучше всего её описывает:

Система управления лифтом
Компилятор языка программирования
Универсальный компьютер

Показать решение

Ключевая идея: У разных моделей разная память и мощность. Сопоставьте требования системы с моделью.

(a) Лифт:

Конечное число конфигураций (этаж, двери, кнопки). Не нужна неограниченная память «истории» и разбор вложенности.

Ответ: FSA — переходы между конечным множеством состояний по нажатиям и датчикам.

(b) Компилятор:

Нужен разбор вложенных конструкций:

Вложенные скобки: ((()))
Вложенные блоки: { { } }
Вложенные вызовы: f(g(h(x)))

Для сопоставления открывающих и закрывающих разделителей нужен стек.

Ответ: PDA — стековый разбор вложенных структур.

(c) Универсальный компьютер:

Может выполнять произвольные алгоритмы, обращаться к памяти по произвольным адресам, решать любую вычислимую задачу.

Ответ: TM — максимальная стандартная вычислительная мощность, эквивалентная произвольному алгоритму.

Итог:

(a) FSA (конечные состояния, внешняя память не нужна)
(b) PDA (стек для вложенности)
(c) TM (полная вычислимость)

4.3. Понимание иерархии мощности (Лекция 1, Пример 3)

Объясните, почему верно утверждение «всякая задача, решаемая FSA, решается и PDA», но обратное неверно.

Показать решение

Ключевая идея: Более мощная модель может имитировать менее мощную, но не наоборот.

Имитация FSA с помощью PDA:
- У PDA есть всё, что у FSA (состояния и переходы), плюс стек
- Чтобы вести себя как FSA, просто не используем стек — не делаем push/pop
- PDA ведёт себя как исходный FSA
- Значит, всё, что решает FSA, решает и PDA
Почему обратное неверно:
- Некоторые задачи нуждаются именно в стеке
- Пример: язык \(L = \{a^n b^n : n \geq 0\}\)
- PDA решает:
  - push каждой \(a\)
  - pop на каждую \(b\)
  - принять, если в конце стек пуст
- FSA не решает:
  - с конечной памятью в состояниях нельзя запомнить произвольное \(n\)
  - после 1000 символов \(a\) нужно отличать 1000 от 1001 — при ограниченном числе states это невозможно (по pigeonhole principle, то есть принципу Дирихле)
Вывод:
- Стек PDA даёт задачи вне возможностей FSA
- PDA строго мощнее FSA

Ответ: PDA может симулировать FSA, игнорируя стек. Но PDA решает стековые задачи (вложенность, \(a^n b^n\)), недоступные FSA, поэтому PDA строго мощнее.

4.4. Проследить выполнение FSA (Лекция 1, Пример 4)

Рассмотрим FSA для строк с чётным числом единиц над \(\{0, 1\}\) со состояниями:

\(q_0\) (EVEN, принимающее): «видели чётное число единиц»
\(q_1\) (ODD, не принимающее): «видели нечётное число единиц»

Проследите работу FSA на входной строке “\(101\)”. Принимает или отвергает?

Показать решение

Ключевая идея: Начинаем с начального состояния и для каждого символа следуем переходу. Принимаем, если конечное состояние принимающее.

Переходы:

Из \(q_0\): \(0\) → \(q_0\); \(1\) → \(q_1\)
Из \(q_1\): \(0\) → \(q_1\); \(1\) → \(q_0\)

Начальное состояние: \(q_0\)
Принимающие: \(\{q_0\}\)

Трассировка для “\(101\)”:

Начало: \(q_0\) (EVEN) — 0 единиц
Читаем \(1\): \(q_0 \to q_1\) (1 единица, ODD)
Читаем \(0\): остаёмся в \(q_1\) (по-прежнему 1 единица)
Читаем \(1\): \(q_1 \to q_0\) (2 единицы, EVEN)
Конец ввода: текущее состояние \(q_0\) — принимающее

Ответ: FSA ПРИНИМАЕТ строку “\(101\)”, потому что конечное состояние \(q_0\) принимающее. Верно: в “\(101\)” две единицы (чётное число).

4.5. Запись языков (Лекция 1, Пример 5)

Для каждого пункта определите, принадлежит ли строка языку:

Принадлежит ли “\(aabb\)” языку \(L = \{a^n b^n : n \geq 0\}\)?
Принадлежит ли “\(aab\)” языку \(L = \{a^n b^n : n \geq 0\}\)?
Принадлежит ли \(\epsilon\) языку \(L = \{a^n b^n : n \geq 0\}\)?

Показать решение

Ключевая идея: Запись \(a^n b^n\) означает «ровно \(n\) символов \(a\), затем ровно \(n\) символов \(b\)» для некоторого целого \(n \geq 0\). Язык объединяет все такие строки.

(a) “\(aabb\)” в \(L\)?

Подсчёт:

число \(a\): 2
число \(b\): 2
равны? да
форма: \(aa\) затем \(bb\) = \(a^2 b^2\)

Это \(a^n b^n\) при \(n = 2\).

Ответ: ДА, “\(aabb\)” \(\in L\)

(b) “\(aab\)” в \(L\)?

число \(a\): 2
число \(b\): 1
равны? нет

Не существует \(n\) с таким шаблоном.

Ответ: НЕТ, “\(aab\)” \(\notin L\)

(c) \(\epsilon\) в \(L\)?

У пустой строки:

число \(a\): 0
число \(b\): 0
равны? да
форма: \(a^0 b^0 = \epsilon\)

Это \(a^n b^n\) при \(n = 0\) (условие \(n \geq 0\) явно допускает \(n = 0\)).

Ответ: ДА, \(\epsilon \in L\)

Правило: при определении с \(n \geq 0\) всегда проверяйте включение пустой строки (\(n = 0\)).